9642. Хорошие пары

Имеются два массива А и В, содержащие n чисел. Пара индексов i и j (i < j) считаются хорошими, если a_i + a_j > b_i + b_j.

Найдите количество пар хороших индексов.

Вход. Первая строка содержит число n (n ≤ 10⁵). Вторая строка содержит n чисел массива А. Третья строка содержит n чисел массива В. Известно, что 0 ≤ a_i, b_i ≤ 10⁹.

Выход. Выведите количество пар хороших индексов.

Пример входа	Пример выхода
6 6 5 8 4 7 0 3 5 1 5 2 3	11

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Перепишем условие a_i + a_j > b_i + b_j в виде: a_i – b_i > – ( a_j – b_j).

Построим массив разностей c, в котором c_i = a_i – b_i. Отсортируем его по возрастанию. Неравенство a_i – b_i > – ( a_j – b_j) эквивалентно c_i > – c_j, или то же самое что c_j > – c_i.

Теперь для каждого индекса i (0 ≤ i ≤ n – 1) следует найти такой минимальный индекс j, что c_j > – c_i. Для всех индексов k таких что j ≤ k ≤ n – 1, пары индексов i и k будут хорошими. Однако чтобы пары индексов не считать дважды, следует выбрать только такие пары (i, k), для которых k > i.

Пример

Рассмотрим приведенный пример. Отсортируем элементы массивов по возрастанию c_i = a_i – b_i.

Пусть i = 0. Ищем наименьший индекс j, что c_j > – c₀ = 3. Таким индексом будет j = 4. Следовательно пары индексов (0, 4) и (0, 5) будут хорошими.

Пусть i = 1. Ищем наименьший индекс j, что c_j > – c₁ = 1. Таким индексом будет j = 3. Следовательно пары индексов (1, 3), (1, 4) и (1, 5) будут хорошими.

Пусть i = 2. Ищем наименьший индекс j, что c_j > – c₂ = 0. Таким индексом будет j = 3. Следовательно пары индексов (2, 3), (2, 4) и (2, 5) будут хорошими.

Пусть i = 3. Ищем наименьший индекс j, что c_j > – c₃ = -3. Таким индексом будет j = 1. Пара (i, k) будет хорошей, если выполняются два условия: k ≥ j и k > i. Пары индексов (3, 4) и (3, 5) будут хорошими. Пары (3, 2) и (3, 1) также будут хорошими, но они были подсчитаны, когда рассматривались i = 1 (пара (1, 3)) и i = 2 (пара (2, 3)).

Пусть i = 4. Единственной хорошей парой будет (4, 5).

Всего имеется 11 пар хороших индексов.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

a.resize(n); b.resize(n); c.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);

for (i = 0; i < n; i++)

scanf("%d", &b[i]);

Строим массив разностей c, в котором c_i = a_i – b_i.

for (i = 0; i < n; i++)

c[i] = a[i] - b[i];

Сортируем массив разностей c.

sort(c.begin(), c.end());

Количество пар хороших индексов подсчитываем в переменной res.

res = 0;

Перебираем индексы i.

for (i = 0; i < n; i++)

{

Для каждого индекса i ищем минимальный индекс pos, что c_pos > – c_i.

pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin();

Если pos ≤ i, то установим pos = i + 1.

if (pos <= i) pos = i + 1;

Хорошими будут пары индексов (i, k), для которых pos ≤ k ≤ n – 1. Таких значений k будет в точности (n – 1) – pos + 1 = n – pos.

res += n - pos;

}

Выводим ответ.

printf("%lld\n", res);